package com.mlh.dp.子序列;

import java.util.Arrays;

/**
 * @author 缪林辉
 * @date 2024/4/29 22:42
 * @DESCRIPTION
 */
// 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
// 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
// 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列
public class 最长递增子序列 {
    //看代码随想录写出
    public int method1(int[] nums) {
        //dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
        //为什么一定表示 “以nums[i]结尾的最长递增子序” ，
        // 因为我们在 做 递增比较的时候，如果比较 nums[j] 和 nums[i] 的大小，
        // 那么两个递增子序列一定分别以nums[j]为结尾 和 nums[i]为结尾，
        // 要不然这个比较就没有意义了，不是尾部元素的比较那么 如何算递增呢。
        int[]dp=new int[nums.length];
        Arrays.fill(dp,1);
        int maxLen=1;
        for (int i = 1; i <nums.length ; i++) {
            for (int j = i-1; j >=0 ; j--) {
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            maxLen=Math.max(maxLen,dp[i]);
        }
        return maxLen;
    }

    public int practice(int[] nums) {
        int len=nums.length;
        int[]dp=new int[len];
        Arrays.fill(dp,1);
        int maxLen=1;
        for (int i = 1; i < len; i++) {
            for (int j = i; j >=0 ; j--) {
                //要把前面的全部遍历了
                //不能只遍历到num[i]第一个大于的数
                //因为没办法确定第一个大于的数就能构成以num[i]结尾的最长子序列
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            maxLen=Math.max(maxLen,dp[i]);
        }
        return maxLen;
    }
}
